
//1091.二进制矩阵中的最短路径
class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        if(grid[0][0]==1) return -1;
        int n=grid.size(),m=grid[0].size();
        int dx[]={0,0,-1,-1,-1,1,1,1};
        int dy[]={-1,1,1,-1,0,1,-1,0};
    
        //此题如果使用DFS会导致已经走过的路径不好处理,如果直接将已经走过的路径禁止掉,就会导致一些更短的路径被裁剪掉
        //所以此题使用BFS更好
        queue<pair<int,int>> q;
        vector<vector<int>> vist(n,vector<int>(m));
        q.push({0,0});
        int ret=0;
        while(!q.empty())
        {
            ret++;
            int _size=q.size();
            for(int i=0;i<_size;i++)
            {
                int x=q.front().first,y=q.front().second;
                vist[x][y]=1;
                q.pop();
                if(x==n-1&&y==m-1) return ret;
                for(int k=0;k<8;k++)
                {
                    int a=x+dx[k],b=y+dy[k];
                    if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]==0&&!vist[a][b]) 
                    {
                        q.push({a,b});
                        vist[a][b]=1;
                    }
                }
            }
        }
        return -1;
    }
};